#include "head/TreeNode.h"
#include <vector>
#include <unordered_map>

using namespace std;
class Solution {
public:
    vector<TreeNode*> allPossibleFBT(int n) {
        if (!memo_.count(n)) {
            vector<TreeNode*> result;
            if (n == 1) {
                result.emplace_back(new TreeNode(0));
            } else if (n % 2 == 1) {
                for (int i = 0; i < n; ++i) {
                    for (const auto& left: allPossibleFBT(i)) {
                        for (const auto& right: allPossibleFBT(n - 1 - i)) {
                            auto node = new TreeNode(0);
                            node->left = left;
                            node->right = right;
                            result.emplace_back(node);
                        }
                    }
                }
            }
            memo_[n] = move(result);
        }
        return memo_[n];
    }

private:
    unordered_map<int, vector<TreeNode*>> memo_;
};
